package com.jhy.suixianglu.daima20221220;

import com.jhy.suixianglu.daima20221212.ListNode;

/**
 * 给定一个链表的头节点  head ，
 * 返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 */
public class DetectCycle {
    public ListNode detectCycle(ListNode head) {
        ListNode cur = head;
        // 定义快指针
        ListNode fast = head;
        // 定义慢指针
        ListNode slow = head;

        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                // 相遇的节点
               ListNode together = fast;
               // 相遇节点和头节点同时出发 相遇的话就是入口
               while (together != cur){
                   together =together.next;
                   cur = cur.next;
               }
               return cur;
            }
        }
        return null;
    }
}
